# 遗传算法
import random

K = 8  # 后代个数(偶数)
N = 8  # 皇后数量


def get_num_of_no_conflict(status):  # 获取该状态下不互相攻击的皇后对数
    num_of_conflict = 0
    for col1 in range(N):
        for col2 in range(col1 + 1, N):
            if (status[col1] == status[col2]) \
                    or ((col2 - col1) == abs(status[col1] - status[col2])):  # 判断是否相互攻击
                num_of_conflict += 1
    return N * (N - 1) / 2 - num_of_conflict  # 此处是求不相互攻击的


def get_parent(all_status, no_conflict_num):  # 按照比例求状态群的某一个状态作为父亲之一
    choose_parent = random.randint(0, sum(no_conflict_num) - 1)
    temp_cmp = no_conflict_num[0]
    index = 0
    while choose_parent >= temp_cmp:
        index += 1
        temp_cmp += no_conflict_num[index]
    return all_status[index]

    # if choose_parent < no_conflict_num[0]:
    #     return all_status[0]
    # elif no_conflict_num[0] <= choose_parent < (no_conflict_num[0] + no_conflict_num[1]):
    #     return all_status[1]
    # elif (no_conflict_num[0] + no_conflict_num[1]) <= choose_parent < (
    #         no_conflict_num[0] + no_conflict_num[1] + no_conflict_num[2]):
    #     return all_status[2]
    # return all_status[3]


def variation(all_status):  # 变异
    for i in range(0, len(all_status)):
        col = random.randint(0, N - 1)
        row = random.randint(0, N - 1)
        all_status[i][col] = row
    return all_status


def inheritance(all_status):  # 杂交
    no_conflict_num = []
    new_all_status = []
    for i in range(K):
        no_conflict_num.append(get_num_of_no_conflict(all_status[i]))
    for t in range(0, int(K/2)):  # 一次生成两个子代，循环两次
        father = get_parent(all_status, no_conflict_num)
        mother = get_parent(all_status, no_conflict_num)
        while father == mother:
            mother = get_parent(all_status, no_conflict_num)
        first_child = father[:]
        second_child = mother[:]
        num = random.randint(0, N - 1)  # 各种交换下标0-num的数，形成子代
        for i in range(0, num + 1):
            first_child[i] = second_child[i]
            second_child[i] = father[i]
        new_all_status.append(first_child)
        new_all_status.append(second_child)
    return new_all_status  # 返回新的状态种族


def find_answer(all_status):  # 判断该状态种族是否有解
    for i in range(0, len(all_status)):
        if get_num_of_no_conflict(all_status[i]) == N * (N - 1) / 2:
            print("find a answer:")
            print(all_status[i])
            return True
    return False


def init_status():
    status = []
    for i in range(N):  # 0~N-1
        status.append(random.randint(0, N - 1))
    return status


all_status = []
for i in range(K):  # 随机生成K个状态，即种族
    status = init_status()
    all_status.append(status)
print("the initial all_status: ")
print(all_status)
all_status = inheritance(all_status)  # 杂交
while not find_answer(all_status):  # 找不到最优后代（最优解）则一直繁衍
    whether_variation = random.randint(1, 10)  # 10%变异的几率
    if whether_variation < 2:
        print("have a variation,and the all_status:")
        all_status = variation(all_status)
        print(all_status)
        print(get_num_of_no_conflict(all_status[0]))
    else:
        all_status = inheritance(all_status)  # 杂交
        print("the next all_status: ")
        print(all_status)
        print(get_num_of_no_conflict(all_status[0]))
